# 组合总和II： https://leetcode-cn.com/problems/combination-sum-ii/

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        rst = []
        candidates.sort()
        def gTargetList(nums, total, idx):
            
            # 如果相等就加入结果列表
            if total == target:
                rst.append(nums[:])
                return 
            # 1. 剪枝大于剪枝
            if total > target: return 
                
            for i in range(idx, len(candidates)):
                # 剪枝掉重复的组合： [1, 3] 剪枝掉 [3, 1], 注意这里不像全排列一样使用 used数组， i > idx， 去掉当前“层”重复的
                if i > idx and candidates[i] == candidates[i-1]:
                    continue
                nums.append(candidates[i])
                gTargetList(nums, total + candidates[i], i + 1)
                nums.pop()

        gTargetList([], 0, 0)
        return rst
